Number of matching subsequences

Time: O(N+W); Space: O(K); medium

Notes:

  • N is the size of S

  • W is the size of words

  • K is the number of words

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Example 1:

Input: S = “abcde”; words = [“a”, “bb”, “acd”, “ace”]

Output: 3

Explanation:

  • There are three words in words that are a subsequence of S: “a” Notes:

  • All words in words and S will only consists of lowercase letters.

  • The length of S will be in the range of [1, 50000].

  • The length of words will be in the range of [1, 5000].

  • The length of words[i] will be in the range of [1, 50].

[1]:

import collections

class Solution1(object):
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        waiting = collections.defaultdict(list)
        for word in words:
            it = iter(word)
            waiting[next(it, None)].append(it)
        for c in S:
            for it in waiting.pop(c, ()):
                waiting[next(it, None)].append(it)
        return len(waiting[None])

[2]:

s = Solution1()
S = "abcde"
words = ["a", "bb", "acd", "ace"]
assert s.numMatchingSubseq(S, words) == 3